#include <stdio.h>

// 交换函数
void Swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 三数取中函数，返回左、中、右三者的中间值索引
int GetMid(int *a, int left, int right) {
    int mid = left + (right - left) / 2;
    if (a[left] > a[right]) {
        Swap(&a[left], &a[right]);
    }
    if (a[mid] > a[right]) {
        Swap(&a[mid], &a[right]);
    }
    if (a[left] < a[mid]) {
        Swap(&a[left], &a[mid]);
    }
    return left;  // 返回基准元素的索引
}

// Hoare 分区法的快速排序
void HoreQuickSort(int *a, int left, int right) {
    if (left >= right) {
        return;
    }

    int begin = left, end = right;
    int key = GetMid(a, left, right);  // 三数取中并将基准值放到left位置
    Swap(&a[left], &a[key]);           // 将基准交换到左端作为参考

    while (begin < end) {
        // 从右往左找到第一个小于基准的元素
        while (begin < end && a[end] >= a[left]) {
            --end;
        }
        // 从左往右找到第一个大于基准的元素
        while (begin < end && a[begin] <= a[left]) {
            ++begin;
        }
        // 交换左右不符合顺序的元素
        if (begin < end) {
            Swap(&a[begin], &a[end]);
        }
    }

    // 最后将基准元素放到分区点
    Swap(&a[left], &a[begin]);

    // 递归排序左右两部分
    HoreQuickSort(a, left, begin - 1);
    HoreQuickSort(a, begin + 1, right);
}

// 打印数组
void print_array(int *a, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}


// 挖坑法快速排序
void HoleQuickSort(int* arr, int left, int right)
{
    if (left >= right)
        return;

    // 使用第一个元素作为基准值（也可以选择其他方式，如三数取中）
    int pivotValue = arr[left];
    int holeIndex = left; // 挖坑的位置，初始化为基准值的位置
    int scanLeft = left, scanRight = right; // 左右扫描指针

    // 从右向左扫描，找到第一个小于基准值的元素
    while (scanRight > scanLeft)
    {
        // 从右向左找到第一个小于基准值的元素
        while (scanRight > scanLeft && arr[scanRight] >= pivotValue)
            scanRight--;

        // 如果找到，将该元素放到坑里（holeIndex位置）
        if (scanRight > scanLeft)
        {
            arr[holeIndex] = arr[scanRight];
            holeIndex = scanRight; // 更新坑的位置到当前元素的位置
        }

        // 从左向右扫描，找到第一个大于基准值的元素
        while (scanRight > scanLeft && arr[scanLeft] <= pivotValue)
            scanLeft++;

        // 如果找到，将该元素放到坑里（此时坑的位置可能已经被更新）
        if (scanRight > scanLeft)
        {
            arr[holeIndex] = arr[scanLeft];
            holeIndex = scanLeft; // 再次更新坑的位置
        }
    }

    // 当左右扫描指针相遇时，将基准值放到坑里
    arr[holeIndex] = pivotValue;

    // 递归排序基准值左右两侧的子数组
    HoleQuickSort(arr, left, holeIndex - 1);
    HoleQuickSort(arr, holeIndex + 1, right);
}

void FbQuickSort(int* a, int left, int right)
{
    if (left >= right)
        return;

    int pre = left;  // 前指针，初始化为 left
    int cur = left + 1;  // 后指针，初始化为 left + 1
    int key = a[left];  // 选择基准元素为 left

    while (cur <= right)
    {
        if (a[cur] < key)  // 如果当前元素小于基准元素
        {
            pre++;  // 前指针右移
            Swap(&a[cur], &a[pre]);  // 交换当前元素与前指针指向的元素
        }
        cur++;  // 后指针继续右移
    }

    // 最后将基准元素与前指针指向的元素交换
    Swap(&a[left], &a[pre]);

    // 递归对左边和右边的子数组进行快速排序
    FbQuickSort(a, left, pre - 1);
    FbQuickSort(a, pre + 1, right);
}


// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    print_array(arr, n);

    HoreQuickSort(arr, 0, n - 1);

    printf("排序后数组: ");
    print_array(arr, n);

    return 0;
}